package 算法.leetcode.linked.list;

import org.junit.Test;

/**
 * 编写一个程序，找到两个单链表相交的起始节点。
 * @author lchenglong
 * @date 2020/12/15
 */
public class IntersectionNode extends LinkListBase{
    @Test
    public void test() {
        ListNode la = new ListNode(4);
        ListNode la2 = new ListNode(1);
        la.next = la2;
        ListNode inter = new ListNode(8);
        la2.next = inter;
        ListNode lb = new ListNode(5);
        ListNode lb2 = new ListNode(6);
        lb.next = lb2;
        lb2.next = inter;

        ListNode c1 = new ListNode(4);
        inter.next = c1;
        ListNode c2 = new ListNode(5);
        c1.next = c2;
        ListNode result = getIntersectionNode(la, lb2);
        System.out.println(result==null?null:result.val);
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pa = headA,pb = headB;
        while (pa!=pb) {
            /**
             * A连表的尾节点指向B连表的头节点，B连表的尾结点指向A连表的头节点，那么AB两链表的长度就一样了
             * 如果AB相交，那么总有AB链表相等的节点出现，此节点即为相交节点
             * 如果AB不相交，那么最后相等的是null
             */
            pa = pa == null?headB:pa.next;
            pb = pb == null?headA:pb.next;
        }
        return pa;
    }


}
